package 排序算法;

import java.util.Arrays;

/*
* 归并排序
* */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr =  {8,4,5,7,1,3,6,2};
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println("合并后的数组"+Arrays.toString(arr));


        int[] arr2 = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr2[i] = (int)(Math.random()*800000);
        }
        int[] temp2 = new int[arr2.length];
        long begin = System.currentTimeMillis();
        mergeSort(arr2,0,arr2.length-1,temp2);
        long end = System.currentTimeMillis();
        System.out.println((end-begin));
    }
    // 分加合
    public static void mergeSort(int[] arr,int left,int right,int [] temp){
        if(left < right){
            int mid = (left+right)/2;
            // 向左递归分解
            mergeSort(arr,left,mid,temp);
            // 向右递归分解
            mergeSort(arr,mid+1,right,temp);
            // 合并
            merge(arr,left,mid,right,temp);
        }
    }

    // 合并
    /**
     * @param arr 排序的原始数组
     * @param left 左边有序序列的索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 中转的临时数组
     */
    public static void merge(int[] arr ,int left, int mid,int right,int[] temp){
        int i = left;
        int j = mid+1;// 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引

        // 1.左右两边的元素按照规则填充到temp数组,直到有一边填充完毕为止
        while(i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                temp[t] = arr[i];
                i++;
            }else{
                temp[t] = arr[j];
                j++;
            }
            t++;
        }
        // 2.将剩余的元素填充到temp数组
            while(j <= right) {
                temp[t] = arr[j];
                j++;
                t++;
            }

            while (i <= mid) {
                temp[t] = arr[i];
                i++;
                t++;
            }

        // 3.将temp数组拷贝回arr
        // 并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        while(tempLeft <= right){
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }
}
